# PROBLEM STATEMENT:
# ==================
# The Latin alphabet contains 26 characters and telephones only have ten digits
# on the keypad. We would like to make it easier to write a message to your
# friend using a sequence of keypresses to indicate the desired characters. The
# letters are mapped onto the digits as 2=ABC, 3=DEF, 4=GHI, 5=JKL, 6=MNO,
# 7=PQRS, 8=TUV, 9=WXYZ. To insert the character B for instance, the program
# would press 22. In order to insert two characters in sequence from the same
# key, the user must pause before pressing the key a second time. The space
# character should be printed to indicate a pause. For example “2 2″ indicates
# AA whereas “22″ indicates B. Each message will consist of only lowercase
# characters a-z and space characters. Pressing zero emits a space. For
# instance, the message “hi” is encoded as “44 444″, “yes” is encoded as
# “999337777″, “foo  bar” (note two spaces) is encoded as “333666 6660022
# 2777″, and “hello world” is encoded as “4433555 555666096667775553″.
#

# SOLUTIONS:
# ==========
# The solution is simple. It uses dictionary to build up mapping table going
# through each letter and transform it. While transforming it also checks if two
# consequtive elements has the same character. If so it adds an extra space.
# This whole thing takes O(n) time complexity.

T9Table = {
   ' ' : '0',
   'a' : '2',
   'b' : '22',
   'c' : '222',
   'd' : '3',
   'e' : '33',
   'f' : '333',
   'g' : '4',
   'h' : '44',
   'i' : '444',
   'j' : '5',
   'k' : '55',
   'l' : '555',
   'm' : '6',
   'n' : '66',
   'o' : '666',
   'p' : '7',
   'q' : '77',
   'r' : '777',
   's' : '7777',
   't' : '8',
   'u' : '88',
   'v' : '888',
   'w' : '9',
   'x' : '99',
   'y' : '999',
   'z' : '9999'
}

def T9Spelling(str):
   seq = ['x']
   for c in str.lower():
      t9 = T9Table[c]
      seq.extend([t9] if seq[-1][0] != t9[0] else [' ', t9])
   return ''.join(seq[1:])
   
print(T9Spelling('AA'))
print(T9Spelling('B'))
print(T9Spelling('hi'))
print(T9Spelling('yes'))
print(T9Spelling('foo bar'))
print(T9Spelling('hello world'))
